Object positioning (localization) system is a technology with broad applicability in many application areas, such as office, healthcare, security, coalmine, subway, smart building, restaurant etc. A necessary feature that a success localization system must have is the multiple access control capability, that with such a mechanism, multiple mobile objects can be localized simultaneously. It is a general requirement of many localization-based applications. The positioning system should simultaneously localize all visitors and provide guidance information accordingly. For patients, doctors and assets tracking in a hospital, there may be many patents, doctors and assets presenting together in the same operating room. Therefore, it is necessary to track multiple objects simultaneously by a location system. Other application scenarios, such as office, subway, smart building and restaurant etc. all need simultaneously tracking of multiple objects.
So far, for the requirement of tracking of multiple mobile objects, an Autonomous Ultrasound Indoor Tracking System (AUITS) was proposed as a highly accurate, highly robust and customer-friendly indoor tracking system. It employs the idea of positioning on one device (POD) and uses Time Of Arrival (TOA) of ultrasound for distance measurement. The POD is a positioning device of a fixed topology structure, which integrates a plurality of ultrasound receivers into a single device and can be installed everywhere according to the user's requirement. The POD is a compact device (looks almost like a Frisbee). When being used, the POD can spread several telescopic rods like the skeleton of an umbrella, and at the end of each rod there is an ultrasound receiver. Since the topology of the extended POD is fixed and the coordinates of such receivers can be calculated easily, manual calibration of the ultrasound receivers' coordinates is no longer needed. Besides this, since all of the receivers are on one device, the complex wireless-based signaling and network protocols are no longer needed. FIG. 1 shows a multi-objects positioning system, which includes two PODs, i.e. R1 and R2. Regarding the detailed description of the AUITS system and the POD, please refer to a Chinese patent application No. 200810006317.0, titled “Positioning on One Device (POD) and Autonomous Ultrasound Positioning System and Method Using the POD”, which was filed by the same applicant of the invention on Jan. 29, 2008. This priority application is incorporated here by reference in its entirety for all purposes.
For purpose of simplicity, the present invention is described by taking the AUITS system and the POD positioning device as an example. However, it can be easily realized from the following detailed description that the principle and technical solution of the present invention is not only limited to the AUITS system and the POD positioning device, but can be applied to other common indoor positioning systems and positioning devices, as long as such positioning systems and devices possess appropriate functions for achieving mobile object tracking.
An example of the AUITS system is shown in FIG. 1, which includes multiple tag devices and multiple PODs. In this example, the AUITS system includes two PODs and three tag devices. The POD is designed as a positioning device with structural topology to be mounted in the monitoring environment for ease of installation and ease of calibration. It consists of a RF transceiver in center and multiple US receivers spreading around. Tag devices T1, T2 and T3 are attached to mobile objects to be tracked by PODs. Each of the tag devices consists of RF transceiver and US transmitter. As shown in FIG. 1, when the AUITS system is in use, a tag device sends RF and US signals to POD. RF signal is used for time synchronization and tag device identification; US signal is used to measure the distances between tag devices and US receivers. Then, the position of the tag device (i.e. the object) can be inferred by POD based on the distance measurements to the multiple US receivers. This invention will mainly address the multiple access control problem of a multi-objects positioning system, such as the AUITS system.
In the AUITS system, design of the multiple access control (MAC) protocol is very crucial, which allows multiple PODs to detect all tag devices correctly and efficiently in their operating range. Especially, for the multi-objects positioning system, such as AUITS, several problems will be posed if an efficient MAC protocol is absent. For example, signal collision may happen in whether RF or Ultrasound transmissions. Thus, it may cause incorrect measurement of TOA, resulting in positioning error. If signal collision happens, time occupied by collided signals will be wasted, resulting in lower capacity. Also, to achieve better coverage and better capacity, multiple PODs may be deployed. However, since multiple tag devices cannot be simultaneously tracked, the densely deployed PODs cannot be sufficiently utilized. The POD resources will be wasted. These problems will pose great challenges in AUITS applications. However, they are only appearances of some essential problems. In order to design an efficient MAC protocol, we need to analyze and address the essence behind the challenging problems. For example, the Hidden Node (HN) problem and the Exposed Node (EN) problem as described below.
FIGS. 2A and 2B are schematic diagrams for explaining the HN and EN problems.
1. Hidden Node (HN) Problem
It is the basic requirement for MAC design to avoid signal collision, that is, MAC should prevent simultaneous transmissions by interfering tag devices caused by HN Problem.
As shown in FIG. 2A, HN problem happens when two tag devices T1 and T2 cannot sense each other's traffic, while they are transmitting simultaneously to the same receiver R (e.g. POD). HN problem will result in positioning error and low capacity. Denote DCS as carrier sense radius of the tag device, DT as transmission distance of the tag device, condition of HN problem is:
                    {                                                                                                                                          T                      1                                        -                                          T                      2                                                                                        >                                  D                  CS                                                                                                                                                                                      T                      1                                        -                    R                                                                    <                                  D                  T                                                                                                                                                                                      T                      2                                        -                    R                                                                    <                                  D                  T                                                                                        (        1        )            
Traditional method to overcome the HN problem is to enlarge DCS, to make DCS>2DT. However, enlarging carrier sense radius may cause another serious problem, i.e. Exposed Node (EN) problem that will be introduced in the following. In addition, regarding the AUITS system, two kinds of physical signal, RF and US signals, are employed for object tracking. Therefore, both RF and US channels should be considered elaborately for anti-collision protocol design. In addition, considering that RF and US are always emitted in pair from tag devices, and the propagation speed of US (around 340 m/s) is much slower than RF and the US is not encoded, these characters should be collaboratively considered and thoroughly in process of MAC protocol design.
2. Exposed Node (EN) Problem
Besides signal collision avoidance, another important requirement for MAC protocol is efficiency, which means the ideal MAC protocol can make full use of the spatio-temporal reuse of RF and US channels so that the AUITS system can be allowed to simultaneously track multiple tag devices s as many as possible. In order to achieve this, the MAC protocol should be designed to resist the Exposed Node (EN) Problem.
As shown in FIG. 2B, EN problem happens when a link was prohibited due to carrier sensing of current link. However, in this case, the intended link will not collide with the current link. In the example shown in FIG. 2B, when the tag device T2 want to transmit to the positioning device R2, it senses carrier of the active traffic of another tag device T1. To avoid collision, T2 will not transmit to R2. Indeed, transmission from T2 to R2 will not collide with the current transmission T1 to R1. Thus, EN problem happens. EN problem will cause waste of POD resources and low capacity. Condition of EN problem is as follow:
                    {                                                                                                                                          T                      1                                        -                                          T                      2                                                                                        <                                  D                  CS                                                                                                                                                                                      T                      1                                        -                                          R                      1                                                                                        <                                  D                  T                                                                                                                                                                                      T                      2                                        -                                          R                      2                                                                                        <                                  D                  T                                                                                                                                                                                      T                      2                                        -                                          R                      1                                                                                        >                                  D                  T                                                                                                                                                                                      T                      1                                        -                                          R                      2                                                                                        >                                  D                  T                                                                                        (        2        )            
In contrary to solution to the HN problem, traditional method to overcome EN problem is to reduce Dcs. Thus, there is a difficulty to find a good balance to solve the HN and EN problems at the same time.
In addition, Fairness is also an important factor to be considered in MAC protocol design. The purpose of fairness is to allow that the different tag devices have statistically similar chances to be localized in the AUITS system. It is not expected that some tag devices are located more frequently and other tag devices seldom.
Based on the above analysis, to design and develop a MAC protocol, it is important to avoid signal collision of RF+US signals, to improve Spatio-temporal reuse and to keep fairness in multiple tag devices tracking of the AUITS system. These are just main goals of the present invention.
There are numerous MAC protocols proposed since 1970 for network and wireless network communication, such as Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA), Time Division Multiple Access (TDMA), etc. The motivation of the above MAC design is to accomplish data communication between mobile node and base station. Such MACs are also applicable for location system with single signal, such as RF-only or ultrasound-only based indoor location system. For example, a RADAR system is proposed in P. Bahl. etc. “RADAR: An In-Building RF-based User Location and Tracking System” in Proc. IEEE INFOCOM, 2000. It is a location system based on received signal strength of 802.11 wireless network which uses the same MAC protocol of 802.11 WLAN. In addition, “Sonitor” system of Pat. No. WO 03/087871 A1 to S. Holm entitled “A system and method for position determination of objects” is an ultrasound-only indoor positioning system to achieve room-granularity location accuracy. Tag devices of the Sonitor transmit 20 kHz to 40 kHz ultrasound signals to receivers located in the listening area. In particular, the Sonitor system uses Carrier Sense Multiple Access technique of ultrasound signal to assign ultrasound channel to tag devices. If the US channel is free, tag device communicates a unique signal to the receivers and then the receivers read the signals, detect arrival time and then forward their detection to a central server.
However, those conventional MAC protocol cannot be used directly for multiple-signal based indoor positioning systems, where different physical signal channels should be jointly considered for MAC protocol design. This is especially true for the AUITS system in which RF and US signals are employed for object tracking. To solve this problem, the most related existing solution is “Cricket” system cited from B. Nissanka, etc. The Cricket Location-Support System is described in “Proceedings of the Sixth International Conference on Mobile Computing and Networking, Boston, Mass., USA, August 2000”. This article is incorporated here by reference in its entirety for all purposes. The “Cricket” system consists of a set of independent, unconnected transmitters installed in a building. Each transmitter can transmit both RF and US signals. FIG. 3 shows a brief structural block diagram of the Cricket system. It is shown in the system of FIG. 3 a transmitter 310 and a receiver 320. The “Cricket” system employs a randomization based MAC protocol in which the transmission time of each transmitter is chosen randomly with a uniform distribution within an interval [T1, T2] ms. As shown in FIG. 3, the transmitter 310 sets transmission time of different beacons by using a random delay means 311. Thus, the broadcasts of different beacons are statistically independent. After a randomly delay, a traffic sensing means 312 of the transmitter 310 senses RF carrier for Dus time. Dus is an expected interval for ultrasound to disappear. The aim to do this is to prevent the collision between new transmission of RF+US and existing RF and US signal from other transmitter. During the Dus, a transmit decide means 313 determines whether the channel is free. If the channel is free during Dus, the transmit decide means 313 indicates a signal transmit means 314 to transmit new RF+US signals. Otherwise, the transmitter continues to wait for a randomized delay until channel is clean. FIG. 3 also shows a receiver 320 as the positioning device side. The receiver 320 includes a signal receive means 322 for receiving RF+US signals from the transmitter, and a location calculate means 323 for calculating the position of the object according to the detection results.
However, the randomization based MAC protocol employed by the Cricket system cannot solve the HN and EN problems. First, taking the case of FIG. 2A as an example and with reference to the block diagram of the Cricket system shown in FIG. 3, a timing chart for the HN problem is shown in FIG. 4A. T1 and T2 first perform random delay, then sense RF carrier during Dus time. Since neither of T1 and T2 can sense the transmission signal each other, both of them decide to transmit signal to the POD R. In turn, the RF+US signals transmitted by the T1 and T2 will collide at the receiver R. Indeed, the “Cricket” system applies a “discarding” method against the FIN problem. That is, if the receiver R receives more than one RF message during Dus, the receiver cannot be certain about which RF message the US signal corresponds, and then the receiver discards the US signal and the RF messages. Although this processing can remove positioning error caused by signal confusion, the channel capacity and resource utilization efficiency are rather low. In addition, by taking the case of FIG. 2B as an example, the EN problem also exists in the Cricket system. As shown in FIG. 4B, T1 and T2 first perform random delay. Then, T1 senses RF carrier during the Dus time and decides to transmit RF+US signal to the POD R1, thereby establishing a path LT1,R1. Next, T2 senses traffic from T1, and will not transmit signal to R2 any more. In this way, the desired transmission between T2 and R2 is forbidden due to carrier sensing. However, indeed, LT2,R2 will not collide with LT1,R1. Thus, it may lead to waste of channel resource. As far, it is not mentioned in the Cricket system how to solve the EN problem.
Other related existing solution is a “Bat” system of U.S. Pat. No. 6,493,649 to Jones entitled “Detection system for determining positional and other information about objects”. The “Bat” system deploys ultrasound receivers on the ceiling of room to be monitored. These receivers are placed in an array and connected by wired network to a controlling base station. An ultrasound transmitter is attached to the object to be tracked. In the Bat system, a centralized TDMA-like MAC protocol was used in which all object transmitters are registered to be allocated a time slot for locating. Periodically, the base station broadcasts an identifier as an RF signal. Simultaneously, the base station sends a synchronization pulse via the wired network to all the connected ultrasound receivers. When an object hears its ID broadcast, it emits an ultrasonic signal. Regarding the TDMA-like protocol presented in the Bat system, its disadvantages include 1) a centralized base station is maintained that needs much cost and efforts; and 2) all object tags should be registered at system bootstrap phase. It is difficult to add a new tag device into system when working. Thus, the flexibility of system is not good. In addition, the key problem to the Bat system is low spatial-temporal reuse of resource. In order to track individual object tag device, it required that all positioning devices will wait for the signal emission of the specific tag in its time slot. However, in fact, there are only a small subset of positioning device can detect and sense the signal from such a tag device and more other devices stay always IDLE state during the period.